package util;

import org.junit.Assert;
import org.junit.Test;

import java.io.FileInputStream;

import static util.GraphAlgorithms.dinic;
import static util.GraphAlgorithms.maximalFlow;
import static util.GraphUtil.*;

/**
 * @author Egor Kulikov (kulikov@devexperts.com)
 */
public class GraphAlgorithmsTest {
	@Test
	public void testMaximalFlow() throws Exception {
		InputReader input = new InputReader(new FileInputStream("src/util/test/graph/flow/input.txt"));
		InputReader output = new InputReader(new FileInputStream("src/util/test/graph/flow/output.txt"));
		int testCount = input.readInt();
		for (int i = 0; i < testCount; i++) {
			int vertexCount = input.readInt();
			Graph graph = new SparseGraph(vertexCount);
			int edgeCount = input.readInt();
			for (int j = 0; j < edgeCount; j++) {
				int source = input.readInt() - 1;
				int destination = input.readInt() - 1;
				int capacity = input.readInt();
				graph.addEdge(new FlowEdge(source, destination, capacity));
			}
			Assert.assertEquals(maximalFlow(graph, 0, vertexCount - 1), output.readInt());
		}
	}

	@Test
	public void testDinic() throws Exception {
		InputReader input = new InputReader(new FileInputStream("src/util/test/graph/flow/input.txt"));
		InputReader output = new InputReader(new FileInputStream("src/util/test/graph/flow/output.txt"));
		int testCount = input.readInt();
		for (int i = 0; i < testCount; i++) {
			int vertexCount = input.readInt();
			Graph graph = new SparseGraph(vertexCount);
			int edgeCount = input.readInt();
			for (int j = 0; j < edgeCount; j++) {
				int source = input.readInt() - 1;
				int destination = input.readInt() - 1;
				int capacity = input.readInt();
				graph.addEdge(new FlowEdge(source, destination, capacity));
			}
			Assert.assertEquals(dinic(graph, 0, vertexCount - 1), output.readInt());
		}
	}
}
